import java.util.Stack;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-10-12
 * Time: 20:41
 */
class  Node{
    public char val;
    public Node left;
    public Node right;

    public Node(char val) {
        this.val = val;
    }
}
public class BinaryTree {
        public Node createTree(){
            Node A=new Node('A');
            Node B=new Node('B');
            Node C=new Node('C');
            Node D=new Node('D');
            Node E=new Node('E');
            Node F=new Node('F');
            Node G=new Node('G');
            Node H=new Node('H');
            A.left=B;
            A.right=C;
            B.left=D;
            B.right=E;
            C.left=F;
            C.right=G;
            E.right=H;
            return A;
        }

    //前序遍历
    void preorderTraversalNor(Node root){
            if(root==null) return;
            Stack<Node>stack=new Stack<>();
            Node cur=root;
            while(cur!=null || !stack.empty()){
                while(cur!=null){
                    stack.push(cur);
                    System.out.print(cur.val+" ");
                    cur=cur.left;
                }
                Node top=stack.pop();
                cur=top.right;
            }
        System.out.println();
    }

    //中序遍历
    void inorderTraversalNor(Node root) {
            if(root==null)return;
            Stack<Node>stack=new Stack<>();
            Node cur=root;
            while(cur!=null || !stack.empty()){
                while(cur!=null){
                    stack.push(cur);
                    cur=cur.left;
                }
                Node top=stack.pop();
                System.out.print(top.val+" ");
                cur=top.right;
            }
        System.out.println();
    }

    //后序遍历
    void postOrderTraversalNor(Node root) {
        if (root == null) return;
        Node prev = null;
        Stack<Node> stack = new Stack<>();
        Node cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            if (cur.right == null || cur.right == prev) {
                stack.pop();
                System.out.print(cur.val + " ");
                prev = cur;
                cur = null;// 这个y被打印了  不能再次入栈
            } else {
                cur = cur.right;
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        Node root=binaryTree.createTree();
        System.out.println("中序遍历：");
        binaryTree.inorderTraversalNor(root);
        System.out.println("后序遍历：");
        binaryTree.postOrderTraversalNor(root);
        System.out.println("前序遍历：");
        binaryTree.preorderTraversalNor(root);
    }
}
